/**
 * 
 */
package leetCode;

/**
 * 最多只删除一个字符，能够成为回文串
 * 
 * @author zhongfang
 *
 */
public class ValidPalindromeII {
	/**
	 * 如果碰到不相等的，则跳过当前i或者跳过j 24.64%
	 * 
	 * @param s
	 * @return
	 */
	public boolean validPalindrome1(String s) {
		int i = 0, j = s.length() - 1;
		while (i < j) {
			if (s.charAt(i) == s.charAt(j)) {
				i++;
				j--;
			} else {
				return heler(s.substring(i, j)) || heler(s.substring(i + 1, j + 1));
			}
		}
		return true;
	}

	private boolean heler(String substring) {
		int i = 0, j = substring.length() - 1;
		while (i < j) {
			if (substring.charAt(i) != substring.charAt(j)) {
				return false;
			}
			i++;
			j--;
		}
		return true;
	}

	/*
	 * 删除最多一个字符，是否是回文 即删除或者不删
	 */
	public boolean validPalindrome222(String s) {
		int n = s.length();
		int[][] dp = new int[n][n];
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				dp[i][j] = -1;
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			dp[i][i] = 0;// 是回文
			for (int j = i + 1; j < n; j++) {
				if (s.charAt(i) == s.charAt(j)) {
					dp[i][j] = dp[i + 1][j - 1];
				} else {
					if (dp[i][j - 1] != -1 && dp[i + 1][j] != -1) {
						dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
					} else if (dp[i][j - 1] == -1 && dp[i + 1][j] == -1) {
						dp[i][j] = -1;
					} else if (dp[i][j - 1] == -1) {
						dp[i][j] = dp[i + 1][j] + 1;
					} else {
						dp[i][j] = dp[i][j - 1] + 1;
					}
				}
			}
		}
		System.out.println(dp[0][n - 1]);
		return dp[0][n - 1] == 1 || dp[0][n - 1] == 0;
	}

	public boolean validPalindrome(String s) {
		boolean chance = true;// 有一次机会不想等
		int i = 0, j = s.length() - 1;
		while (i < j) {
			if (s.charAt(i) == s.charAt(j)) {
				i++;
				j--;
			} else {
				if (chance) {
					chance = false;
				} else {
					return false;
				}
				i++;
			}
		}
		return true;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(new ValidPalindromeII().validPalindrome("abc"));
	}
}
